package com.javaspeak.algorithm.prime.sieveoferatosthenes;

import java.util.ArrayList;
import java.util.List;

/**
 * Using Sieve of Eratosthenes to generate Prime Numbers
 * <p>
 * The idea behind the algorithm is that if we know a small number is prime
 * then we can mark all multiples of itself as being NOT Prime. e.g. if 3 is
 * prime then 3x2, 3x3, 3x4, 3x5, 3x6, e.t.c must all be NOT Prime.
 * <p>
 * If we need to find all prime numbers up to and including 14 then we do as
 * follows:
 * <p>
 * (i) Mark all numbers 2 to 14 as prime (even though they are not all prime)
 * <p>
 * 2=P, 3=P, 4=P, 5=P, 6=P, 7=P, 8=P, 9=P, 10=P, 11=P, 12=P, 13=P, 14=P
 * <p>
 * (ii) Starting with 2 find all multiples of itself and mark as not prime (NP).
 * e.g. 4, 6, 8, 10, 12, 14 should all be marked as NP
 * <p>
 * 2=P, 3=P, 4=NP, 5=P, 6=NP, 7=P, 8=NP, 9=P, 10=NP, 11=P, 12=NP, 13=P, 14=NP
 * <p>
 * (iii) get the next number after 2, e.g. 3, if it is prime mark all
 * multiples of itself as not prime, e.g 6, 9, 12 should be marked NP
 * <p>
 * 2=P, 3=P, 4=NP, 5=P, 6=NP, 7=P, 8=NP, 9=NP, 10=NP, 11=P, 12=NP, 13=P, 14=NP
 * <p>
 * (iv) get the next number after 3, e.g. 4, if it is not prime do nothing
 * <p>
 * (v) get the next number after 4, e.g. 5, if it is prime mark all
 * multiples of itself as not prime. e.g. 10 should be marked NP
 * 2=P, 3=P, 4=NP, 5=P, 6=NP, 7=P, 8=NP, 9=NP, 10=NP, 11=P, 12=NP, 13=P, 14=NP
 * <p>
 * (vi) 6 do nothing because is not prime
 * <p>
 * <vi) 7 mark 14 as prime
 * <p>
 * (vii) 8 stop as 8 x 2 is more than 14
 *
 * @author John Dickerson
 */
public class CreatePrimeNumbers {

    /**
     * Creates a list of prime numbers up to and including "number"
     *
     * @param number
     * @return
     */
    public static List<Long> createPrimeNumbers( int number ){

        List<Long> primeNumbers = new ArrayList<Long>();

        boolean[] isPrime = new boolean[ number + 1 ];

        // mark all numbers from 2 up to and including "number" as prime
        // (even though they are not all prime)
        for ( int i=2; i<=number; i++ ){

            isPrime[ i ] = true;
        }

        // For each number from 2 upwards check if it is prime. If it is not
        // prime do nothing.  If the number is prime mark all multiples of
        // itself as being NOT prime.  i.e. if i=3 and number=14 then mark
        // 6, 9, 12 as being NOT Prime
        for ( int i=2; i<=number; i++ ){

            if ( isPrime[ i ] ){

                for ( int j=2; ( j * i ) < number; j++ ){

                    isPrime[ j * i ] = false;
                }
            }
        }

        // now loop through array and for each element check if is true. If
        // it is true that means the index is a prime number
        for ( int i=2; i<=number; i++ ){

            if ( isPrime[ i ] ){

                primeNumbers.add( new Long( i ) );
            }
        }

        return primeNumbers;
    }
}
